markdown
Union-Find の基本
lecture/information/algorithm/data-structures/Union-Find の基本-講義.n.md
Union-Find の基本
algorithmdata-structuresundergraduatelecture
導入
この講義で最重要なのは、Union-Find は「この 2 つがつながっているか」を毎回グラフ全体から調べるのではなく、属している集合を代表元で管理する構造だということです。
辺を 1 本ずつ足していく問題では、そのたびに DFS や BFS を回すと重いことがあります。Union-Find は、連結している仲間をまとめて持つことで、その判定を軽くします。
用語と定義
Union-Find とは、互いに交わらない集合の分割を管理する構造です。
代表元 とは、ある集合を代表する要素です。
方針
まず各要素がどの集合に属するかを、親をたどって代表元へ辿る形で持ちます。そのあと、2 つの集合を結合するときは代表元どうしをつなぎます。
直感的な説明
生徒をいくつかの班に分けていて、「A さんと B さんは同じ班か」をすぐ知りたいとします。班長を 1 人 決めておけば、「A さんの班長と B さんの班長が同じか」を見れば済みます。Union-Find はこれを計算機で行う道具です。
厳密な説明
1. find
ある要素の代表元を探す操作です。
2. union
2 つの要素が属する集合を 1 つにまとめる操作です。
3. 使いどころ
辺を順番に足しながら連結性を管理する問題で役に立ちます。
見分け方
- 「つながっているか」だけを何度も問うなら、Union-Find を疑います。
- 最短路そのものを求める問題には、そのままでは向きません。
最終形
\boxed{\text{find}=\text{代表元を探す}}
\boxed{\text{union}=\text{集合を結合する}}
一言でいうと
- Union-Find は、連結成分を代表元で管理して、「つながっているか」を軽く判定する構造です。